#include<iostream>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
using namespace std;
// int main(){
//     vector<int> myhouse(4);
//     myhouse.push_back(1);
//     myhouse.push_back(2);
//     myhouse.push_back(1);
//     myhouse.push_back(2);
//     // for(int i=0;i<5;i++){
//     //     myhouse[i]=10-i;
//     // }
//     // for(vector<int>::iterator it=myhouse.begin();it<myhouse.end();it++){
//     //     cout<<it;
//     // }
//     sort(myhouse.begin(),myhouse.end());
//     // for(int i=0;i<myhouse.size();i++){
//     //     cout<<myhouse[i]<<endl;
//     // }
//     // cout<<myhouse<<endl;
//     int sum=0;int k=1;
//         for(int i=0;i<myhouse.size();i++){
//             for(int j=i+1;j<myhouse.size();j++){
//                 if(myhouse[j]-myhouse[i]==k){
//                     sum+=1;
//                }
//                 else if(myhouse[j]-myhouse[i]<k){
//                     break;
//                }
//                 else {
//                    j=myhouse.size();
//                }
//             }
//         }
//         // return sum;
//         cout<<sum;
//     return 0;
// }
// int main(){
    // string s="12312131243534";
    // for(int i=0;i<s.size();i++){
    //     int a=s[i]-48;
    //     cout<<a;
    // }
    // return 0;
    // unsigned int b=123;
    // int a=b;
    // cout<<b;
    // vector<int> a;
//     a.push_back(1);
//     a.push_back(2);
//     a.push_back(3);
//     a.erase(2);
//     for(int i=0;i<a.size();i++){
//         cout<<a[i]<<" ";
         
//     }
// }
// int main(){
//     enum course{
//         math,Chinses,english,che
//     };
//     enum c=english;
//     cout<<english<<endl;
//     map<int,float> myMap;
//     myMap.insert(1,1.0);
//     myMap.find(1);
    
// }
// #include<bits/stdc++.h>
// using namespace std;
// 1101010110010101101001110000000000000000000000000000000000000000000
// 1101010110010101101001101000010010101101110011011111111001110110011
// int main(){
// 	float num;
// 	while(cin>>num){
// 		vector<int> tem;
// 		while(num>0){
// 			float a=floor(num/2);
//             cout<<a*2<<" ";
// 			if(a*2!=num){
// 				tem.push_back(1);
// 			}
// 			else {tem.push_back(0);}
// 			num=a;
// 		}
// 		for(int i=tem.size()-1;i>=0;i--){
// 			cout<<tem[i];
// 		}
// 		cout<<endl;
// 	}
// }
// int main(){
// 	string str;
// 	while(cin>>str){
// 		vector<int> result;
// 		while(str.length()){
// 			if(((int)str[str.length()-1]-48)%2==0){
// 				result.push_back(0);
// 			}
// 			else{
//                 result.push_back(1);
//             }
// 			vector<char> tem;
// 			bool flag=false;
// 			for(int i=0;i<str.length();i++){
// 				int a;
// 				if(flag) 
// 					 a=(int)str[i]-38;
// 				else 
// 					 a=(int)str[i]-48;
// 				flag=false;
// 				if(a%2>0){
// 					flag=true;
// 				}
// 				a=a/2;
//                 if(a!=0||i!=0) tem.push_back(a+48);
// 			}	
// 			string s;
// 			for(int i=0;i<tem.size();i++){
// 				s+=tem[i];	
// 			}
//             str=s;
//             cout<<str<<" ";
// 		}
// 		for(int i=result.size()-0;i>=0;i--){
// 			cout<<result[i];
// 		}
// 			cout<<endl;
// 	}
// }
// 0110100000101100
// 110100000101100
// int main(){
// 	char a='A';
// 	cout<<(int)a;
	
// }
// int main(){
// 	string str;
// 	while(cin>>str){
// 		int result=0;
// 		int n=0;
// 		for(int i=str.length()-1;i>=2;i--){
// 			int a=(int)str[i]-48;
// 			if(a>10) a-=7;
// 			cout<<a<<" ";
// 			result+=a*pow(16,n);
// 			n++;
// 		}
// 		cout<<result;
// 	}
// }xw
// int main(){
// 	unsigned int a;
// 	while(cin>>a){
// 		vector<char> result;
// 		while(a!=0){
// 		if(a%2==0){
// 			result.push_back('0');
// 		}
// 		else{
// 			result.push_back('1');
// 		}
// 		a=a/2;
// 		cout<<a;
// 		cout<<endl;
// 	}
// 	for(int i=result.size()-1;i>0;i--){
// 			cout<<result[i];
// 			// cout<<1;
// 		}
// 	}
// }
// int main(){
// 	int a;
// 	while(cin>>a){
// 		vector<char> tem;
// 		while(a!=0){
// 			if(a%(-2)!=0){
// 				tem.push_back('1');
// 			}
// 			else{
// 				tem.push_back('0');
// 			}
// 			a=a/(-2);
//             cout<<a<<" ";
// 		}
// 		for(int i=tem.size()-1;i>=0;i--){
// 			// cout<<tem[i];
// 		}
// 		cout<<endl;
// 	}
// }
// int main(){
//     char a='A';
//    cout<<10+'a';
//     string str="1231";

// }
// inline int dex10(string s,int n){
// 	int sum=s[0]-'0';
// 	for(int i=1;i<s.length();i++){
//         cout<<sum<<" ";
// 		sum*=n;
// 	}
// 	return sum;
// }
// int main(){
//     string str="A9";
//     int n=dex10(str,16);
//     cout<<n;
// }
// int main(){
// 	int n;
// 	cin>>n;
// 	int a[n][n];
//     for(int i=0;i<n;i++){
// 		for(int j=0;j<n;j++){
// 			a[i][j]=0;
// 		}
// 	}
// 	int number=1;
//     int direction[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
// 	int direct=0;
// 	int i=0;int j=0;
// 	while(number<=pow(n,2)){
// 		a[i][j]=number;
//         cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
// 		if(i+direction[direct][0]>=n||i+direction[direct][0]<0||j+direction[direct][1]>=n||j+direction[direct][1]<0||a[i+direction[direct][0]][j+direction[direct][1]]!=0){
//             direct=(direct+1)%4;
//         }
//         i+=direction[direct][0];
//         j+=direction[direct][1];
//         number++;
// 	}
// 	for(int i=0;i<n;i++){
// 		for(int j=0;j<n;j++){
// 			cout<<a[i][j]<<" ";
// 		}
// 		cout<<endl;
// 	}
// }
// inline int isXuanzhuan(int n){
// 	int a[n][n];
// 	int b[n][n];
// 		for(int i=0;i<n;i++){
// 			for(int j=0;j<n;j++){
// 				cin>>a[i][j];
// 			}
// 		}
// 		for(int i=0;i<n;i++){
// 			for(int j=0;j<n;j++){
// 				cin>>b[i][j];
// 			}
// 		}
// 		if(a[0][0]==b[0][0]){
// 			for(int i=0;i<n;i++){
// 				for(int j=0;j<n;j++){
// 					if(a[i][j]!=b[i][j]){
//                         i=n;
//                         break;
// 					}
// 					if(i==n-1&&j==n-1){
// 						return 0;
// 					}
// 				}
// 			}
// 		}
// 		if(a[0][0]==b[0][n-1]){
// 			for(int i=0;i<n;i++){
// 				for(int j=0;j<n;j++){
// 					if(a[i][j]!=b[j][n-1-i]){
//                         i=n;
//                         break;
// 					}
// 					if(i==n-1&&j==n-1){
// 						return 90;
// 					}
// 				}
// 			}
// 		}
// 		if(a[0][0]==b[n-1][n-1]){
// 			for(int i=0;i<n;i++){
// 				for(int j=0;j<n;j++){
// 					if(a[i][j]!=b[n-1-i][n-1-j]){
// 						i=n;
//                         break;
// 					}
// 					if(i==n-1&&j==n-1){
// 						return 180;
// 					}
// 				}
// 			}
// 		}
// 		if(a[0][0]==b[n-1][0]){
//                 for(int i=0;i<n;i++){
//                     for(int j=0;j<n;j++){
//                         if(a[i][j]!=b[n-j-1][i]){
//                            i=n;
//                            break;
//                         }
//                         if(i==n-1&&j==n-1){
//                             return 270;
//                         }
//                     }
//                 }
//             }
// 		return -1;
// }
// int main(){
// 	int n;
// 	while(cin>>n){
// 		cout<<isXuanzhuan(n)<<endl;
// 	}
// }
// void up(int a[4][4]){
// 	int i=0;
//     bool flag=false;
// 	while(i<4){
// 		for(int j=0;j<3;j++){
// 			if(a[j][i]==a[j+1][i]&&a[j][i]!=0){
// 				a[j][i]+=a[j][i];
// 				a[j+1][i]=0;
//                 flag=true;
// 			}
// 		}
//         if(flag){
//             for(int j=3;j>0;j--){
//                 if(a[j-1][i]==0&&a[j][i]!=0){
//                     a[j-1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//             for(int j=3;j>0;j--){
//                 if(a[j-1][i]==0&&a[j][i]!=0){
//                     a[j-1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//             flag=false;
//         }
//         else{
//             for(int j=3;j>0;j--){
//                     if(a[j-1][i]==0&&a[j][i]!=0){
//                         a[j-1][i]=a[j][i];
//                         a[j][i]=0;
//                     }
//                 }
//         }
// 		i++;
// 	}
// }
// void down(int a[4][4]){
// 	int i=0;
//     bool flag=false;
// 	while(i<4){
// 		for(int j=3;j>0;j--){
// 			if(a[j][i]==a[j-1][i]&&a[j][i]!=0){
// 				a[j][i]+=a[j][i];
// 				a[j-1][i]=0;
//                 flag=true;
// 			}
// 		}
//         if(flag){
//             for(int j=0;j<3;j++){
//                 if(a[j][i]!=0&&a[j+1][i]==0){
//                     a[j+1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//             for(int j=0;j<3;j++){
//                 if(a[j][i]!=0&&a[j+1][i]==0){
//                     a[j+1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//             flag=false;
//         }
//         else{
//             for(int j=0;j<3;j++){
//                 if(a[j][i]!=0&&a[j+1][i]==0){
//                     a[j+1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//         }
// 		i++;
// 	}
// }
// void left(int a[4][4]){
// 	int i=0;
//     bool flag=false;
// 	while(i<4){
// 		for(int j=0;j<3;j++){
// 			if(a[i][j]==a[i][j+1]&&a[i][j]!=0){
// 				a[i][j]+=a[i][j];
// 				a[i][j+1]=0;
//                 flag=true;
// 			}
// 		}
//         if(flag){
//             for(int j=3;j>0;j--){
//                 if(a[i][j]!=0&&a[i][j-1]==0){
//                     a[i][j-1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//             for(int j=3;j>0;j--){
//                 if(a[i][j]!=0&&a[i][j-1]==0){
//                     a[i][j-1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//             flag=false;
//         }
//         else{
//             for(int j=3;j>0;j--){
//                 if(a[i][j]!=0&&a[i][j-1]==0){
//                     a[i][j-1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//         }
// 		i++;
// 	}
// }
// void right(int a[4][4]){
// 	int i=0;
//     bool flag=false;
// 	while(i<4){
// 		for(int j=3;j>0;j--){
// 			if(a[i][j]==a[i][j-1]&&a[i][j]!=0){
// 				a[i][j]+=a[i][j];
// 				a[i][j-1]=0;
//                 flag=true;
// 			}
// 		}
//         if(flag){
//             for(int j=0;j<3;j++){
//                 if(a[i][j]!=0&&a[i][j+1]==0){
//                     a[i][j+1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//             for(int j=0;j<3;j++){
//                 if(a[i][j]!=0&&a[i][j+1]==0){
//                     a[i][j+1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//             flag=false;
//         }
//         else{
//             for(int j=0;j<3;j++){
//                 if(a[i][j]!=0&&a[i][j+1]==0){
//                     a[i][j+1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//         }
// 		i++;
// 	}
// }
// int main(){
// 	int flag;
// 	cin>>flag;
// 	int a[4][4];
// 	for(int i=0;i<4;i++){
// 		for(int j=0;j<4;j++){
// 			cin>>a[i][j];
// 		}
// 	}
// 	switch(flag){
// 		case 1:up(a);break;
// 		case 2:down(a);break;
// 		case 3:left(a);break;
// 		case 4:right(a);break;
// 	}
// 	for(int i=0;i<4;i++){
// 		for(int j=0;j<4;j++){
// 			cout<<a[i][j]<<" ";
// 		}
// 		cout<<endl;
// 	}
// }
// void up(int a[4][4]){
// 	int i=0;
//     bool flag=false;
// 	while(i<4){
//         int num=0;
//         for(int j=0;j<4;j++){
//             if(a[j][i]!=0){
//                 num++;
//             }
//         }
//         while(num>0){
//             for(int j=3;j>0;j--){
//                 if(a[j-1][i]==0&&a[j][i]!=0){
//                     a[j-1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//             num--;
//         }
// 		for(int j=0;j<3;j++){
// 			if(a[j][i]==a[j+1][i]&&a[j][i]!=0){
// 				a[j][i]+=a[j][i];
// 				a[j+1][i]=0;
//                 flag=true;
// 			}
// 		}
//         if(flag){
//             for(int j=3;j>0;j--){
//                 if(a[j-1][i]==0&&a[j][i]!=0){
//                     a[j-1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//             for(int j=3;j>0;j--){
//                 if(a[j-1][i]==0&&a[j][i]!=0){
//                     a[j-1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//             flag=false;
//         }
// 		i++;
// 	}
// }
// void down(int a[4][4]){
// 	int i=0;
//     bool flag=false;
// 	while(i<4){
//         int num=0;
//         for(int j=0;j<4;j++){
//                 if(a[j][i]!=0){
//                     num++;
//                 }
//         }
//         while(num>0){
//             for(int j=0;j<3;j++){
//                 if(a[j][i]!=0&&a[j+1][i]==0){
//                     a[j+1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//             num--;
//         }
// 		for(int j=3;j>0;j--){
// 			if(a[j][i]==a[j-1][i]&&a[j][i]!=0){
// 				a[j][i]+=a[j][i];
// 				a[j-1][i]=0;
//                 flag=true;
// 			}
// 		}
//         if(flag){
//             for(int j=0;j<3;j++){
//                 if(a[j][i]!=0&&a[j+1][i]==0){
//                     a[j+1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//             for(int j=0;j<3;j++){
//                 if(a[j][i]!=0&&a[j+1][i]==0){
//                     a[j+1][i]=a[j][i];
//                     a[j][i]=0;
//                 }
//             }
//             flag=false;
//         }
// 		i++;
// 	}
// }
// void left(int a[4][4]){
// 	int i=0;
//     bool flag=false;
// 	while(i<4){
//         int num=0;
//         for(int j=0;j<4;j++){
//                 if(a[i][j]!=0){
//                     num++;
//                 }
//         }
//         while(num>0){
// 		    for(int j=3;j>0;j--){
//                 if(a[i][j]!=0&&a[i][j-1]==0){
//                     a[i][j-1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//             num--;
//         }
// 		for(int j=0;j<3;j++){
// 			if(a[i][j]==a[i][j+1]&&a[i][j]!=0){
// 				a[i][j]+=a[i][j];
// 				a[i][j+1]=0;
//                 flag=true;
// 			}
// 		}
//         if(flag){
//             for(int j=3;j>0;j--){
//                 if(a[i][j]!=0&&a[i][j-1]==0){
//                     a[i][j-1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//             for(int j=3;j>0;j--){
//                 if(a[i][j]!=0&&a[i][j-1]==0){
//                     a[i][j-1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//             flag=false;
//         }
// 		i++;
// 	}
// }
// void right(int a[4][4]){
// 	int i=0;
//     bool flag=false;
// 	while(i<4){
//         int num=0;
//         for(int j=0;j<4;j++){
//                 if(a[i][j]!=0){
//                     num++;
//                 }
//         }
//         while(num>0){
// 		    for(int j=0;j<3;j++){
//                 if(a[i][j]!=0&&a[i][j+1]==0){
//                     a[i][j+1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//             num--;
//         }
// 		for(int j=3;j>0;j--){
// 			if(a[i][j]==a[i][j-1]&&a[i][j]!=0){
// 				a[i][j]+=a[i][j];
// 				a[i][j-1]=0;
//                 flag=true;
// 			}
// 		}
//         if(flag){
//             for(int j=0;j<3;j++){
//                 if(a[i][j]!=0&&a[i][j+1]==0){
//                     a[i][j+1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//             for(int j=0;j<3;j++){
//                 if(a[i][j]!=0&&a[i][j+1]==0){
//                     a[i][j+1]=a[i][j];
//                     a[i][j]=0;
//                 }
//             }
//             flag=false;
//         }
// 		i++;
// 	}
// }
// int main(){
// 	int flag;
// 	cin>>flag;
// 	int a[4][4];
// 	for(int i=0;i<4;i++){
// 		for(int j=0;j<4;j++){
// 			cin>>a[i][j];
// 		}
// 	}
// 	switch(flag){
// 		case 1:up(a);break;
// 		case 2:down(a);break;
// 		case 3:left(a);break;
// 		case 4:right(a);break;
// 	}
// 	for(int i=0;i<4;i++){
// 		for(int j=0;j<4;j++){
// 			cout<<a[i][j]<<" ";
// 		}
// 		cout<<endl;
// 	}
// }
// 判断两个日期之间有多天
// bool isYear(int year){
// 	if((year%4==0)&&(year%100!=0)) return true;
// 	if(year%400==0) return true;
// 	return false;
// }
// void swap(int m,int n){
//     int tem=m;
//     m=n;
//     n=tem;
// }
// int makeOneYear(int year1,int month1,int year2,int month2){
// 	int num=0;
// 	if(year1==year2) return num;
// 	if(month1<3){
//         while(year1<year2){
//             if(isYear(year1)){
//                 num+=366;
//             }
//             else num+=365;
//             year1++;
//         }
//     }
//     else{
//         while(year1<year2){
//             year1++;
//              if(isYear(year1)){
//                 num+=366;
//             }
//             else num+=365;
//         }
//     }
//     return num;
// }
// int main(){
// 	int year1,month1,day1;
// 	int year2,month2,day2;
//     int c[12]={31,28,31,30,31,30,31,31,30,31,30,31};
// 	while(~scanf("%4d%2d%2d",&year1,&month1,&day1)){
// 		scanf("%4d%2d%2d",&year2,&month2,&day2);
// 		if(year1>year2){
//             swap(year1,year2);
//             swap(month1,month2);
//             swap(day1,day2);
//         }
//         int n=makeOneYear(year1,month1,year2,month2);
//         if(month1<month2){
//             n+=c[month1-1];
//             month1++;
//         }
//         else if(month1>month2){
//             n-=c[month1-2];
//             month1--;
//         }
//         n+=day2-day1+1;
//         if(month1<2&&month2>2){
//                 n+=1;
//         }
//         if(month1>2&&month2<2){
//                 n-=1;
//         }
//         cout<<n<<endl;
// 	}
// }
// 格式化输出一年第n天的日期
// bool isYear(int year){
// 	if((year%4==0)&&(year%100!=0)) return true;
// 	if(year%400==0) return true;
// 	return false;
// }
// int main(){
// 	int year,day;
// 	int a[12]={31,28,31,30,31,30,31,31,30,31,30,31};
// 	int b[12]={31,29,31,30,31,30,31,31,30,31,30,31};
// 	while(cin>>year>>day){
// 		int month=0;
// 		int date;
// 		if(isYear(year)){
//             cout<<"yes"<<endl;
// 			while(day>b[month]){
// 				day-=b[month];
// 				month++;
// 			}
// 			date=day;
// 			month++;
// 			cout<<year<<"-";
// 			if(month<10) cout<<"0";
// 			cout<<month<<"-";
// 			if(date<10) cout<<"0";
// 			cout<<date<<endl;
// 		}
// 		else{
//             cout<<"no"<<endl;
// 			while(day>a[month]){
// 				day-=a[month];
// 				month++;
// 			}
// 			date=day;
// 			month++;
// 			cout<<year<<"-";
// 			if(month<10) cout<<"0";
// 			cout<<month<<"-";
// 			if(date<10) cout<<"0";
// 			cout<<date<<endl;
// 		}	
// 	}
// }
// 日期累加问题，给定日期之后多少天为多少日期
// bool isYear(int year){
// 	if((year%4==0)&&(year%100!=0)) return true;
// 	if(year%400==0) return true;
// 	return false;
// }
// int main(){
// 	int n;
// 	cin>>n;
// 	while(n>0){
// 		int a[12]={31,28,31,30,31,30,31,31,30,31,30,31};
// 		int year;int month;int day;int date;
// 		cin>>year>>month>>day>>date;
// 		if(isYear(year)&&month>2){
// 			while(month>1){
//                 month--;
// 				date+=a[month-1];
// 			}
// 			date+=day+1;
// 		}
// 		else{
// 			while(month>1){
//                 month--;
// 				date+=a[month-1];
// 			}
// 			date+=day;
//             cout<<date;
// 		}
// 		while(date>366){
//             cout<<date<<endl;
// 			if(isYear(year)){
// 				date-=366;
// 				year++;
//                 cout<<" "<<"yes";
// 			}
// 			else{
// 				date-=365;
// 				year++;
//                 cout<<" "<<"no";
// 			}
// 		}
// 		if(date==366&&isYear(year)){
// 			month=12;
// 			day=31;
// 		}
// 		else if(date==366){
// 			year++;
// 			month=1;
// 			day=1;
// 		}
// 		else{
// 			if(isYear(year)){
// 				a[1]=29;
// 				while(date>a[month-1]){
// 					date-=a[month-1];
// 					month++;
//                     cout<<date<<endl;
// 				}
// 				day=date;
// 			}
// 			else{
// 				while(date>a[month-1]){
// 					date-=a[month-1];
// 					month++;
// 				}
// 				day=date;
// 			}
				
// 		}
// 		cout<<year<<"-";
// 		if(month<10) cout<<"0";
// 		cout<<month<<"-";
// 		if(day<10) cout<<"0";
// 		cout<<day<<endl;
// 		n--;
// 	}
// }
// 浙大上机，统计字符串出现的次数
// int main(){
//     string father;
//     string son;
//     while(son!="#")
//     {
//         getline(cin,son);
//         getline(cin,father);
//         for(int i=0;i<son.length();i++){
//             int num=0;
//             cout<<son[i]<<" ";
//             for(int j=0;j<father.length();j++){
//                 if(father[j]==son[i]){
//                     num++;
//                 }
//             }
//             cout<<num<<endl;
//         }

//     }
// }
// 统计字符串中个数问题（ASCI）
// int main()
// {
//     string str;
//     int englishNum=0;
//     int numberNum=0;
//     int nullNum=0;
//     int elseNum=0;
//     getline(cin,str);
//     for(int i=0;i<str.length();i++){
//         if((str[i]-'a'>=0&&str[i]-'a'<=25)||(str[i]-'A'<=0&&str[i]-'A'>=0)){
//                 englishNum++;
//         }
//         else if(str[i]-'0'>=0&&str[i]-'0'<=9){
//                 numberNum++;
//         }
//         else if(str[i]==32){
//             nullNum++;
//         }
//         else elseNum++;
//      }
//     cout<<englishNum<<" "<<numberNum<<" "<<nullNum<<" "<<elseNum;
// }
// 北京大学上机：讲一个句子中的单词改为首字母大写
// bool isLittleChar(char ch){
//     if(ch-'a'>=0&&ch-'a'<=25){
//         return true;
//     }
//     return false;
// }
// char litterToBig(char ch){
//     return ch-32;
// }
// int main(){
//     string str;
//     getline(cin,str);
//     if(isLittleChar(str[0])){
//         str[0]=litterToBig(str[0]);
//     }
//     for(int i=1;i<str.length()-1;i++){
//         if(str[i]==' '||str[i]=='\t'||str[i]=='\n'||str[i]=='\r'){
//             if(isLittleChar(str[i+1])){
//                 str[i+1]=litterToBig(str[i+1]);
//             }
//         }
//     }
//     cout<<str;
// }
// 北京大学上机：统计子串出现的次数
// 注意这道题中map的使用
// int main(){
//     string str;
//     cin>>str;
//     map<string,int> keyMap;
//     for(int i=0;i<str.length();i++){
//         for(int j=i;j<str.length();j++){
//             string tem=str.substr(i,j-i+1);
//             keyMap[tem]++;
//         }
//     }
//     for(map<string,int>::iterator it=keyMap.begin();it!=keyMap.end();it++){
//         if(it->second>1){
//             cout<<it->first<<" "<<it->second<<endl;
//         }
//     }
// }
// 贵州大学上机：加密算法,转为后三位字母
// int isZimu(char s){
//     if((s-'a'>=0&&s-'a'<=22)||(s-'A'<=22&&s-'A'>=0)){
//         return 1;
//     }
//     if((s-'a'>22&&s-'a'<=25)||(s-'A'>22&&s-'A'<=25)){
//         return 2;
//     }
//     return -1;
// }
// int main(){
//     string str;
//     getline(cin,str);
//     for(int i=0;i<str.length();i++){
//         if(isZimu(str[i])==1){
//             str[i]=str[i]+3;
//         }
//         else if(isZimu(str[i])==2){
//             str[i]=str[i]-23;
//         }
//     }
//     cout<<str;
// }
// 贵州大学上机：删除字符串
// bool isZichuan(string str){
//     if((str[0]=='g'||str[0]=='G')&&(str[1]=='z'||str[1]=='Z')&&(str[2]=='u'||str[2]=='U')) return true;
//     return false;
// }
// int main(){
//     string str;
//     cin>>str;
//     for(int i=0;i<str.length()-2;i++){
//         if(isZichuan(str.substr(i,3))){
//             str.erase(i,3);
//         }
//     }
//     cout<<str;
// }
// 贵州大学上机：字符移动
// int main(){
//     string str;
//     cin>>str;
//     vector<char> ziMu;
//     vector<char> num;
//     for(int i=0;i<str.length();i++){
//         if((str[i]-'0'<=9)&&(str[i]-'0'>=0))
//             num.push_back(str[i]);
//         else    ziMu.push_back(str[i]);
//     }
//     string res="";
//     for(int i=0;i<ziMu.size();i++){
//         res+=ziMu[i];
//     }
//     for(int i=0;i<num.size();i++){
//         res+=num[i];
//     }
//     cout<<res;
// }
// cn_com_southsoft_gms=8e313f93-5911-4440-a4c7-432d7c967e28; NSC_Xfc-DpoufouTxjudi-443=ffffffff096ca61a45525d5f4f58455e445a4a423660
// 上交上机：统计大写字母A-Z出现的次数
// int main(){
//     string strF="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
//     string str;
//     cin>>str;
//     map<char,int> m;
//     for(int i=0;i<str.length();i++){
//         if(str[i]-'A'>=0&&str[i]-'A'<=25){
//             m[str[i]]++;
//         }
//     }
//     for(int i=0;i<strF.length();i++){
//         if(m.count(strF[i])>0){
//             cout<<strF[i]<<":"<<m[strF[i]]<<endl;
//         }
//         else{
//             cout<<strF[i]<<":0"<<endl;
//         }
//     }
// }
// 华科上机：统计单词数量
// int main(){
//     string str;
//     while(cin>>str){
//         if(str[str.length()-1]!='.')
//             cout<<str.length()<<" ";
//         else if(str.length()>1)
//             cout<<str.length()-1;
//     }
// }
// 清华上机：成绩排序/75分答案
// bool compare0(pair<string,int>  a,pair<string,int>  b){
//     return a.second>b.second;
// }
// bool compare1(pair<string,int>  a,pair<string,int>  b){
//      return a.second<b.second;
// }
// int main(){
//     int n;
//     cin>>n;
//     int paixu;
//     cin>>paixu;
//     vector< pair<string, int> > temArray;
//     for(int i=0;i<n;i++){
//         string str;int tem;
//         cin>>str>>tem;
//         temArray.push_back(make_pair(str,tem));
//     }
//     if(paixu==0){
//         stable_sort(temArray.begin(),temArray.end(),compare0);
//     }
//     else{
//         stable_sort(temArray.begin(),temArray.end(),compare1); 
//     }
//     for(int i=0;i<n;i++){
//         cout<<temArray[i].first<<" "<<temArray[i].second<<endl;
//     }
// }
// 贵州大学上机/兰州大学上机：
// int main(){
//     vector<int> one;
//     vector<int> two;
//     int n;
//     cin>>n;
//     for(int i=0;i<n;i++){
//         int tem;
//         cin>>tem;
//         if(tem%2==0){
//             two.push_back(tem);
//         }
//         else{
//             one.push_back(tem);
//         }
//     }
//     sort(two.begin(),two.end());
//     sort(one.begin(),one.end());
//     for(int i=0;i<one.size();i++){
//         cout<<one[i]<<" ";
//     }
//     for(int i=0;i<two.size();i++){
//         cout<<two[i]<<" ";
//     }
// }
// 各种排序算法
// void zhijiePaixu(int a[],int size){
//     for(int i=0;i<size-1;i++){
//         int j=i+1;
        
//         int k=j;
//         while(a[k-1]>a[j]&&k>0){
//             k--;
//         }
//         int tem=a[j];
//         while(j>k){
//             a[j]=a[j-1];
//             j--;
//         }
//         a[k]=tem;
//     }
// }
// void syetemOut(int a[],int size){
//     for(int i=0;i<size;i++){
//         cout<<a[i]<<" ";
//     }
//     cout<<endl;
// }
// void yibanXier(int a[],int size){
//     int n=size/2;
//     for(int i=0;i<n;i++){
//         if(a[i]>a[i+n]){
//             int tem=a[i];
//             a[i]=a[i+n];
//             a[i+n]=tem;
//         }
//     }
// }
// void zhijieXuanzePaixu(int a[],int size){
//     for(int i=0;i<size;i++){
//         int k=i;
//         int tem=INT_MAX;
//         for(int j=i;j<size;j++){
//             if(tem>a[j]){
//                 tem=a[j];
//                 k=j;
//             }
//         }
//         int b=a[i];
//         a[i]=a[k];
//         a[k]=b;
//     }
// }
// void quickSort(int a[],int low,int high){
//     int tem=a[low];
//     int i=low+1;
//     int j=high;
//     while(i<j){
//         while(a[j]>tem&&i<j){
//             j--;
//         }
//         while(a[i]<tem&&i<j){
//             i++;
//         }
//         if(i!=j){
//             int b=a[i];
//             a[i]=a[j];
//             a[j]=b;
//         }
//     }
//     if(a[low]>a[i]){
//         for(int k=low;k<i;k++){
//             a[k]=a[k+1];
//         }
//         a[i]=tem;
//     }
//     else{
//         i=low;
//     }
//     if(low<i-1){
//         quickSort(a,low,i-1);
//     }
//     if(high>i+1){
//         quickSort(a,i+1,high);
//     }
// }
// void erluGuibing(int a[],int size){
//     for(int i=0;i<size-1;i+=2){
//         if(a[i]>a[i+1]){
//             int tem=a[i];
//             a[i]=a[i+1];
//             a[i+1]=tem;
//         }
//     }
// }
// int main(){
//     int n;
//     cin>>n;
//     int a[n];
//     int tem[n];
//     for(int i=0;i<n;i++){
//         cin>>a[i];
//     }
//     for(int i=0;i<n;i++){
//         tem[i]=a[i];
//     }
//     zhijiePaixu(tem,n);
//     syetemOut(tem,n);
//     for(int i=0;i<n;i++){
//         tem[i]=a[i];
//     }
//     yibanXier(tem,n);
//     syetemOut(tem,n);
//     for(int i=0;i<n;i++){
//         tem[i]=a[i];
//     }
//     zhijieXuanzePaixu(tem,n);
//     syetemOut(tem,n);
//     for(int i=0;i<n;i++){
//         tem[i]=a[i];
//     }
//     quickSort(tem,0,n-1);
//     syetemOut(tem,n);
//     for(int i=0;i<n;i++){
//         tem[i]=a[i];
//     }
//     erluGuibing(tem,n);
//     syetemOut(tem,n);
// }
int main(){
    cout<<(0+8)/2;
}
